package 字串;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author TTDB
 * @create 2025/9/13
 * @description: 字节面试题
 */
public class maxSlidingWindow {
    //k为窗口大小
    public int[] maxSlidingWindow(int[] nums, int k)
    {
        int n = nums.length;
        int[] res = new int[n - k + 1]; //返回数组
        //我们保证窗口的单调性,里面存放索引----单调队列
        Deque<Integer> q = new LinkedList<>();

        for(int i = 0; i < n; i++)
        {
            //1.进入， 移除这个窗口中比我小的元素，从Last移除
            while(!q.isEmpty() && nums[q.getLast()] < nums[i]){
                q.removeLast();
            }
            //移除完毕再添加当前索引
            q.addLast(i);

            //2.维持窗口大小,移除队首元素，即最早加入窗口的索引
            int left = i - k + 1;
            if(left > q.getFirst())
                q.removeFirst();

            //3.窗口左端点记录答案
            if(left >= 0){
                // 由于队首到队尾单调递减，所以窗口最大值就在队首
                res[left] = nums[q.getFirst()];
            }
        }
        return res;
    }
}
